package src.BlueBridge.GreedyStrategyAndDynamicProgramming;

import java.util.Scanner;

/**
    有1 5 10 50 100 500元的硬币各有c1 c5 c10 c100 c500枚
    现在要用这些硬币来支付A元，最少需要多少枚硬币
    假定本题至少存在一种支付方案
    输入:
    第一行有六个数字，分别代表从小到大六种面值的硬币的个数
    第二行为A，代表需要支付的A元
    样例:
    输入:
    3 2 1 3 0 2
    620
    输出:
    6
 */

public class _1硬币支付问题 {

    static int[] counts = new int[6];
    static int[] coins = {1, 5, 10, 50, 100, 500};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 0 ; i < 6 ; i++) {
            counts[i] = sc.nextInt();
        }
        int A = sc.nextInt();
        int res = f(A, coins.length - 1);
        System.out.println(res);
    }

    /**
     * 尽量先使用大面值，因为不用大面值，将使用更多的小面值硬币，一定得不到最优解
     * @param A
     * @param cur
     * @return
     */
    public static int f(int A, int cur) {
        if (A <= 0)
            return 0;
        if (cur == 0)
            return A;

        int coinValue = coins[cur];
        // 金额有多少个coinValue
        int x = A / coinValue;
        // 当前面值的硬币数量的个数
        int count = counts[cur];
        int t = Math.min(x, count);
        // 用t个当前面值，剩下的继续处理
        return t + f(A - t * coinValue, cur - 1);
    }
}
